//===--- TypeCheckGeneric.cpp - Generics ----------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// This file implements support for generics.
//
//===----------------------------------------------------------------------===//
#include "polarphp/sema/internal/TypeChecker.h"
#include "polarphp/sema/internal/TypeCheckType.h"
#include "polarphp/ast/DiagnosticsSema.h"
#include "polarphp/ast/ExistentialLayout.h"
#include "polarphp/ast/GenericEnvironment.h"
#include "polarphp/ast/GenericSignatureBuilder.h"
#include "polarphp/ast/InterfaceConformance.h"
#include "polarphp/ast/ParameterList.h"
#include "polarphp/ast/TypeCheckRequests.h"
#include "polarphp/ast/TypeResolutionStage.h"
#include "polarphp/ast/Types.h"
#include "polarphp/basic/Defer.h"
#include "llvm/Support/ErrorHandling.h"

using namespace polar;

///
/// Common code for generic functions, generic types
///

std::string
TypeChecker::gatherGenericParamBindingsText(
   ArrayRef<Type> types,
   TypeArrayView<GenericTypeParamType> genericParams,
   TypeSubstitutionFn substitutions) {
   llvm::SmallPtrSet<GenericTypeParamType *, 2> knownGenericParams;
   for (auto type : types) {
      if (type.isNull()) continue;

      type.visit([&](Type type) {
         if (auto gp = type->getAs<GenericTypeParamType>()) {
            knownGenericParams.insert(
               gp->getCanonicalType()->castTo<GenericTypeParamType>());
         }
      });
   }

   if (knownGenericParams.empty())
      return "";

   SmallString<128> result;
   for (auto gp : genericParams) {
      auto canonGP = gp->getCanonicalType()->castTo<GenericTypeParamType>();
      if (!knownGenericParams.count(canonGP))
         continue;

      if (result.empty())
         result += " [with ";
      else
         result += ", ";
      result += gp->getName().str();
      result += " = ";

      auto type = substitutions(canonGP);
      if (!type)
         return "";

      result += type.getString();
   }

   result += "]";
   return result.str().str();
}

//
// Generic functions
//

/// Get the opaque type representing the return type of a declaration, or
/// create it if it does not yet exist.
llvm::Expected<OpaqueTypeDecl *>
OpaqueResultTypeRequest::evaluate(Evaluator &evaluator,
                                  ValueDecl *originatingDecl) const {
   auto *repr = originatingDecl->getOpaqueResultTypeRepr();
   assert(repr && "Declaration does not have an opaque result type");
   auto *dc = originatingDecl->getInnermostDeclContext();
   auto &ctx = dc->getAstContext();

   // Interface requirements can't have opaque return types.
   //
   // TODO: Maybe one day we could treat this as sugar for an associated type.
   if (isa<InterfaceDecl>(originatingDecl->getDeclContext())
       && originatingDecl->isInterfaceRequirement()) {

      SourceLoc fixitLoc;
      if (auto vd = dyn_cast<VarDecl>(originatingDecl)) {
         fixitLoc = vd->getParentPatternBinding()->getStartLoc();
      } else {
         fixitLoc = originatingDecl->getStartLoc();
      }

      ctx.Diags.diagnose(repr->getLoc(),
                         diag::opaque_type_in_protocol_requirement)
         .fixItInsert(fixitLoc, "associatedtype <#AssocType#>\n")
         .fixItReplace(repr->getSourceRange(), "<#AssocType#>");

      return nullptr;
   }

   // Check the availability of the opaque type runtime support.
   if (!ctx.LangOpts.DisableAvailabilityChecking) {
      auto runningOS =
         TypeChecker::overApproximateAvailabilityAtLocation(
            repr->getLoc(),
            originatingDecl->getInnermostDeclContext());
      auto availability = ctx.getOpaqueTypeAvailability();
      if (!runningOS.isContainedIn(availability)) {
         TypeChecker::diagnosePotentialOpaqueTypeUnavailability(
            repr->getSourceRange(),
            originatingDecl->getInnermostDeclContext(),
            UnavailabilityReason::requiresVersionRange(availability.getOSVersion()));
      }
   }

   // Try to resolve the constraint repr. It should be some kind of existential
   // type.
   TypeResolutionOptions options(TypeResolverContext::GenericRequirement);
   TypeLoc constraintTypeLoc(repr->getConstraint());
   // Pass along the error type if resolving the repr failed.
   auto resolution = TypeResolution::forInterface(
      dc, dc->getGenericSignatureOfContext());
   bool validationError
      = TypeChecker::validateType(ctx, constraintTypeLoc, resolution, options);
   auto constraintType = constraintTypeLoc.getType();
   if (validationError)
      return nullptr;

   // Error out if the constraint type isn't a class or existential type.
   if (!constraintType->getClassOrBoundGenericClass()
       && !constraintType->isExistentialType()) {
      ctx.Diags.diagnose(repr->getConstraint()->getLoc(),
                         diag::opaque_type_invalid_constraint);
      return nullptr;
   }

   if (constraintType->hasArchetype())
      constraintType = constraintType->mapTypeOutOfContext();

   // Create a generic signature for the opaque environment. This is the outer
   // generic signature with an added generic parameter representing the opaque
   // type and its interface constraints.
   auto originatingDC = originatingDecl->getInnermostDeclContext();
   unsigned returnTypeDepth = 0;
   auto outerGenericSignature = originatingDC->getGenericSignatureOfContext();

   if (outerGenericSignature) {
      returnTypeDepth =
         outerGenericSignature->getGenericParams().back()->getDepth() + 1;
   }

   auto returnTypeParam = GenericTypeParamType::get(returnTypeDepth, 0, ctx);

   SmallVector<GenericTypeParamType *, 2> genericParamTypes;
   genericParamTypes.push_back(returnTypeParam);

   SmallVector<Requirement, 2> requirements;
   if (constraintType->getClassOrBoundGenericClass()) {
      requirements.push_back(Requirement(RequirementKind::Superclass,
                                         returnTypeParam, constraintType));
   } else {
      auto constraints = constraintType->getExistentialLayout();
      if (auto superclass = constraints.getSuperclass()) {
         requirements.push_back(Requirement(RequirementKind::Superclass,
                                            returnTypeParam, superclass));
      }
      for (auto protocol : constraints.getInterfaces()) {
         requirements.push_back(Requirement(RequirementKind::Conformance,
                                            returnTypeParam, protocol));
      }
      if (auto layout = constraints.getLayoutConstraint()) {
         requirements.push_back(Requirement(RequirementKind::Layout,
                                            returnTypeParam, layout));
      }
   }

   auto interfaceSignature = evaluateOrDefault(
      ctx.evaluator,
      AbstractGenericSignatureRequest{
         outerGenericSignature.getPointer(),
         std::move(genericParamTypes),
         std::move(requirements)},
      GenericSignature());

   // Create the OpaqueTypeDecl for the result type.
   // It has the same parent context and generic environment as the originating
   // decl.
   auto parentDC = originatingDecl->getDeclContext();
   auto originatingGenericContext = originatingDecl->getAsGenericContext();
   GenericParamList *genericParams = originatingGenericContext
                                     ? originatingGenericContext->getGenericParams()
                                     : nullptr;

   auto opaqueDecl = new (ctx) OpaqueTypeDecl(originatingDecl,
                                              genericParams,
                                              parentDC,
                                              interfaceSignature,
                                              returnTypeParam);
   opaqueDecl->copyFormalAccessFrom(originatingDecl);
   if (auto originatingSig = originatingDC->getGenericSignatureOfContext()) {
      opaqueDecl->setGenericSignature(originatingSig);
   }

   // The declared interface type is an opaque ArchetypeType.
   SubstitutionMap subs;
   if (outerGenericSignature) {
      subs = outerGenericSignature->getIdentitySubstitutionMap();
   }
   auto opaqueTy = OpaqueTypeArchetypeType::get(opaqueDecl, subs);
   auto metatype = MetatypeType::get(opaqueTy);
   opaqueDecl->setInterfaceType(metatype);
   return opaqueDecl;
}

/// Determine whether the given type is \c Self, an associated type of \c Self,
/// or a concrete type.
static bool isSelfDerivedOrConcrete(Type protoSelf, Type type) {
   // Check for a concrete type.
   if (!type->hasTypeParameter())
      return true;

   if (type->isTypeParameter() &&
       type->getRootGenericParam()->isEqual(protoSelf))
      return true;

   return false;
}

// For a generic requirement in a protocol, make sure that the requirement
// set didn't add any requirements to Self or its associated types.
void TypeChecker::checkInterfaceSelfRequirements(ValueDecl *decl) {
   // For a generic requirement in a protocol, make sure that the requirement
   // set didn't add any requirements to Self or its associated types.
   if (auto *proto = dyn_cast<InterfaceDecl>(decl->getDeclContext())) {
      auto &ctx = proto->getAstContext();
      auto protoSelf = proto->getSelfInterfaceType();
      auto sig = decl->getInnermostDeclContext()->getGenericSignatureOfContext();
      for (auto req : sig->getRequirements()) {
         // If one of the types in the requirement is dependent on a non-Self
         // type parameter, this requirement is okay.
         if (!isSelfDerivedOrConcrete(protoSelf, req.getFirstType()) ||
             !isSelfDerivedOrConcrete(protoSelf, req.getSecondType()))
            continue;

         // The conformance of 'Self' to the protocol is okay.
         if (req.getKind() == RequirementKind::Conformance &&
             req.getSecondType()->getAs<InterfaceType>()->getDecl() == proto &&
             req.getFirstType()->is<GenericTypeParamType>())
            continue;

         ctx.Diags.diagnose(decl,
                            diag::requirement_restricts_self,
                            decl->getDescriptiveKind(), decl->getFullName(),
                            req.getFirstType().getString(),
                            static_cast<unsigned>(req.getKind()),
                            req.getSecondType().getString());
      }
   }
}

/// All generic parameters of a generic function must be referenced in the
/// declaration's type, otherwise we have no way to infer them.
void TypeChecker::checkReferencedGenericParams(GenericContext *dc) {
   // Don't do this check for accessors: they're not used directly, so we
   // never need to infer their generic arguments.  This is mostly a
   // compile-time optimization, but it also avoids problems with accessors
   // like 'read' and 'modify' that would arise due to yields not being
   // part of the formal type.
   if (isa<AccessorDecl>(dc))
      return;

   auto *genericParams = dc->getGenericParams();
   auto genericSig = dc->getGenericSignatureOfContext();
   if (!genericParams)
      return;

   auto *decl = cast<ValueDecl>(dc->getInnermostDeclarationDeclContext());

   // A helper class to collect referenced generic type parameters
   // and dependent member types.
   class ReferencedGenericTypeWalker : public TypeWalker {
      SmallPtrSet<CanType, 4> ReferencedGenericParams;

   public:
      ReferencedGenericTypeWalker() {}
      Action walkToTypePre(Type ty) override {
         // Find generic parameters or dependent member types.
         // Once such a type is found, don't recurse into its children.
         if (!ty->hasTypeParameter())
            return Action::SkipChildren;
         if (ty->isTypeParameter()) {
            ReferencedGenericParams.insert(ty->getCanonicalType());
            return Action::SkipChildren;
         }
         return Action::Continue;
      }

      SmallPtrSetImpl<CanType> &getReferencedGenericParams() {
         return ReferencedGenericParams;
      }
   };

   // Collect all generic params referenced in parameter types and
   // return type.
   ReferencedGenericTypeWalker paramsAndResultWalker;
   auto *funcTy = decl->getInterfaceType()->castTo<GenericFunctionType>();
   for (const auto &param : funcTy->getParams())
      param.getPlainType().walk(paramsAndResultWalker);
   funcTy->getResult().walk(paramsAndResultWalker);

   // Set of generic params referenced in parameter types,
   // return type or requirements.
   auto &referencedGenericParams =
      paramsAndResultWalker.getReferencedGenericParams();

   // Check if at least one of the generic params in the requirement refers
   // to an already referenced generic parameter. If this is the case,
   // then the other type is also considered as referenced, because
   // it is used to put requirements on the first type.
   auto reqTypesVisitor = [&referencedGenericParams](Requirement req) -> bool {
      Type first;
      Type second;

      switch (req.getKind()) {
         case RequirementKind::Superclass:
         case RequirementKind::SameType:
            second = req.getSecondType();
            LLVM_FALLTHROUGH;

         case RequirementKind::Conformance:
         case RequirementKind::Layout:
            first = req.getFirstType();
            break;
      }

      // Collect generic parameter types referenced by types used in a requirement.
      ReferencedGenericTypeWalker walker;
      if (first && first->hasTypeParameter())
         first.walk(walker);
      if (second && second->hasTypeParameter())
         second.walk(walker);
      auto &genericParamsUsedByRequirementTypes =
         walker.getReferencedGenericParams();

      // If at least one of the collected generic types or a root generic
      // parameter of dependent member types is known to be referenced by
      // parameter types, return types or other types known to be "referenced",
      // then all the types used in the requirement are considered to be
      // referenced, because they are used to defined something that is known
      // to be referenced.
      bool foundNewReferencedGenericParam = false;
      if (std::any_of(genericParamsUsedByRequirementTypes.begin(),
                      genericParamsUsedByRequirementTypes.end(),
                      [&referencedGenericParams](CanType t) {
                         assert(t->isTypeParameter());
                         return referencedGenericParams.find(
                            t->getRootGenericParam()
                               ->getCanonicalType()) !=
                                referencedGenericParams.end();
                      })) {
         std::for_each(genericParamsUsedByRequirementTypes.begin(),
                       genericParamsUsedByRequirementTypes.end(),
                       [&referencedGenericParams,
                          &foundNewReferencedGenericParam](CanType t) {
                          // Add only generic type parameters, but ignore any
                          // dependent member types, because requirement
                          // on a dependent member type does not provide enough
                          // information to infer the base generic type
                          // parameter.
                          if (!t->is<GenericTypeParamType>())
                             return;
                          if (referencedGenericParams.insert(t).second)
                             foundNewReferencedGenericParam = true;
                       });
      }
      return foundNewReferencedGenericParam;
   };

   ArrayRef<Requirement> requirements;

   auto FindReferencedGenericParamsInRequirements =
      [&requirements, genericSig, &reqTypesVisitor] {
         requirements = genericSig->getRequirements();
         // Try to find new referenced generic parameter types in requirements until
         // we reach a fix point. We need to iterate until a fix point, because we
         // may have e.g. chains of same-type requirements like:
         // not-yet-referenced-T1 == not-yet-referenced-T2.DepType2,
         // not-yet-referenced-T2 == not-yet-referenced-T3.DepType3,
         // not-yet-referenced-T3 == referenced-T4.DepType4.
         // When we process the first of these requirements, we don't know yet that
         // T2
         // will be referenced, because T3 will be referenced,
         // because T3 == T4.DepType4.
         while (true) {
            bool foundNewReferencedGenericParam = false;
            for (auto req : requirements) {
               if (reqTypesVisitor(req))
                  foundNewReferencedGenericParam = true;
            }
            if (!foundNewReferencedGenericParam)
               break;
         }
      };

   // Find the depth of the function's own generic parameters.
   unsigned fnGenericParamsDepth = genericParams->getParams().front()->getDepth();

   // Check that every generic parameter type from the signature is
   // among referencedGenericParams.
   for (auto *genParam : genericSig->getGenericParams()) {
      auto *paramDecl = genParam->getDecl();
      if (paramDecl->getDepth() != fnGenericParamsDepth)
         continue;
      if (!referencedGenericParams.count(genParam->getCanonicalType())) {
         // Lazily search for generic params that are indirectly used in the
         // function signature. Do it only if there is a generic parameter
         // that is not known to be referenced yet.
         if (requirements.empty()) {
            FindReferencedGenericParamsInRequirements();
            // Nothing to do if this generic parameter is considered to be
            // referenced after analyzing the requirements from the generic
            // signature.
            if (referencedGenericParams.count(genParam->getCanonicalType()))
               continue;
         }
         // Produce an error that this generic parameter cannot be bound.
         paramDecl->diagnose(diag::unreferenced_generic_parameter,
                             paramDecl->getNameStr());
         decl->setInvalid();
      }
   }
}

///
/// Generic types
///

GenericSignature TypeChecker::checkGenericSignature(
   GenericParamList *genericParamList,
   DeclContext *dc,
   GenericSignature parentSig,
   bool allowConcreteGenericParams,
   SmallVector<Requirement, 2> additionalRequirements,
   SmallVector<TypeLoc, 2> inferenceSources) {
   assert(genericParamList && "Missing generic parameters?");

   auto request = InferredGenericSignatureRequest{
      dc->getParentModule(), parentSig.getPointer(), genericParamList,
      additionalRequirements, inferenceSources,
      allowConcreteGenericParams};
   auto sig = evaluateOrDefault(dc->getAstContext().evaluator,
                                request, nullptr);

   // Debugging of the generic signature builder and generic signature
   // generation.
   if (dc->getAstContext().TypeCheckerOpts.DebugGenericSignatures) {
      if (auto *VD = dyn_cast_or_null<ValueDecl>(dc->getAsDecl())) {
         VD->dumpRef(llvm::errs());
      } else {
         dc->printContext(llvm::errs());
      }
      llvm::errs() << "\n";
      llvm::errs() << "Generic signature: ";
      sig->print(llvm::errs());
      llvm::errs() << "\n";
      llvm::errs() << "Canonical generic signature: ";
      sig->getCanonicalSignature()->print(llvm::errs());
      llvm::errs() << "\n";
   }

   return sig;
}

/// Form the interface type of an extension from the raw type and the
/// extension's list of generic parameters.
static Type formExtensionInterfaceType(
   ExtensionDecl *ext, Type type,
   GenericParamList *genericParams,
   SmallVectorImpl<Requirement> &sameTypeReqs,
   bool &mustInferRequirements) {
   if (type->is<ErrorType>())
      return type;

   // Find the nominal type declaration and its parent type.
   if (type->is<InterfaceCompositionType>())
      type = type->getCanonicalType();

   Type parentType = type->getNominalParent();
   GenericTypeDecl *genericDecl = type->getAnyGeneric();

   // Reconstruct the parent, if there is one.
   if (parentType) {
      // Build the nested extension type.
      auto parentGenericParams = genericDecl->getGenericParams()
                                 ? genericParams->getOuterParameters()
                                 : genericParams;
      parentType =
         formExtensionInterfaceType(ext, parentType, parentGenericParams,
                                    sameTypeReqs, mustInferRequirements);
   }

   // Find the nominal type.
   auto nominal = dyn_cast<NominalTypeDecl>(genericDecl);
   auto typealias = dyn_cast<TypeAliasDecl>(genericDecl);
   if (!nominal) {
      Type underlyingType = typealias->getUnderlyingType();
      nominal = underlyingType->getNominalOrBoundGenericNominal();
   }

   // Form the result.
   Type resultType;
   SmallVector<Type, 2> genericArgs;
   if (!nominal->isGeneric() || isa<InterfaceDecl>(nominal)) {
      resultType = NominalType::get(nominal, parentType,
                                    nominal->getAstContext());
   } else {
      auto currentBoundType = type->getAs<BoundGenericType>();

      // Form the bound generic type with the type parameters provided.
      unsigned gpIndex = 0;
      for (auto gp : *genericParams) {
         POLAR_DEFER { ++gpIndex; };

         auto gpType = gp->getDeclaredInterfaceType();
         genericArgs.push_back(gpType);

         if (currentBoundType) {
            sameTypeReqs.emplace_back(RequirementKind::SameType, gpType,
                                      currentBoundType->getGenericArgs()[gpIndex]);
         }
      }

      resultType = BoundGenericType::get(nominal, parentType, genericArgs);
   }

   // If we have a typealias, try to form type sugar.
   if (typealias && TypeChecker::isPassThroughTypealias(
      typealias, typealias->getUnderlyingType(), nominal)) {
      auto typealiasSig = typealias->getGenericSignature();
      SubstitutionMap subMap;
      if (typealiasSig) {
         subMap = typealiasSig->getIdentitySubstitutionMap();

         mustInferRequirements = true;
      }

      resultType = TypeAliasType::get(typealias, parentType, subMap, resultType);
   }


   return resultType;
}

/// Retrieve the generic parameter depth of the extended type.
static unsigned getExtendedTypeGenericDepth(ExtensionDecl *ext) {
   auto nominal = ext->getSelfNominalTypeDecl();
   if (!nominal) return static_cast<unsigned>(-1);

   auto sig = nominal->getGenericSignatureOfContext();
   if (!sig) return static_cast<unsigned>(-1);

   return sig->getGenericParams().back()->getDepth();
}

llvm::Expected<GenericSignature>
GenericSignatureRequest::evaluate(Evaluator &evaluator,
                                  GenericContext *GC) const {
   // The signature of a Interface is trivial (Self: TheInterface) so let's compute
   // it.
   if (auto PD = dyn_cast<InterfaceDecl>(GC)) {
      auto self = PD->getSelfInterfaceType()->castTo<GenericTypeParamType>();
      auto req =
         Requirement(RequirementKind::Conformance, self, PD->getDeclaredType());
      auto sig = GenericSignature::get({self}, {req});

      // Debugging of the generic signature builder and generic signature
      // generation.
      if (GC->getAstContext().TypeCheckerOpts.DebugGenericSignatures) {
         PD->printContext(llvm::errs());
         llvm::errs() << "\n";
         llvm::errs() << "Generic signature: ";
         sig->print(llvm::errs());
         llvm::errs() << "\n";
         llvm::errs() << "Canonical generic signature: ";
         sig->getCanonicalSignature()->print(llvm::errs());
         llvm::errs() << "\n";
      }
      return sig;
   }

   // We can fast-path computing the generic signature of non-generic
   // declarations by re-using the parent context's signature.
   auto *gp = GC->getGenericParams();
   if (!gp) {
      return GC->getParent()->getGenericSignatureOfContext();
   }

   // Setup the depth of the generic parameters.
   gp->setDepth(GC->getGenericContextDepth());

   // Accessors can always use the generic context of their storage
   // declarations. This is a compile-time optimization since it lets us
   // avoid the requirements-gathering phase, but it also simplifies that
   // work for accessors which don't mention the value type in their formal
   // signatures (like the read and modify coroutines, since yield types
   // aren't tracked in the AST type yet).
   if (auto accessor = dyn_cast<AccessorDecl>(GC->getAsDecl())) {
      return cast<SubscriptDecl>(accessor->getStorage())->getGenericSignature();
   }

   auto parentSig = GC->getParent()->getGenericSignatureOfContext();
   bool allowConcreteGenericParams = false;
   SmallVector<TypeLoc, 2> inferenceSources;
   SmallVector<Requirement, 2> sameTypeReqs;
   if (auto VD = dyn_cast_or_null<ValueDecl>(GC->getAsDecl())) {
      auto func = dyn_cast<AbstractFunctionDecl>(VD);
      auto subscr = dyn_cast<SubscriptDecl>(VD);

      // For functions and subscripts, resolve the parameter and result types and
      // note them as inference sources.
      if (subscr || func) {
         // Gather requirements from the parameter list.
         auto resolution = TypeResolution::forStructural(GC);

         TypeResolutionOptions options =
            (func ? TypeResolverContext::AbstractFunctionDecl
                  : TypeResolverContext::SubscriptDecl);

         auto params = func ? func->getParameters() : subscr->getIndices();
         for (auto param : *params) {
            auto *typeRepr = param->getTypeRepr();
            if (typeRepr == nullptr)
               continue;

            auto paramOptions = options;
            paramOptions.setContext(param->isVariadic()
                                    ? TypeResolverContext::VariadicFunctionInput
                                    : TypeResolverContext::FunctionInput);
            paramOptions |= TypeResolutionFlags::Direct;

            auto type = resolution.resolveType(typeRepr, paramOptions);

            if (auto *specifier = dyn_cast<SpecifierTypeRepr>(typeRepr))
               typeRepr = specifier->getBase();

            inferenceSources.emplace_back(typeRepr, type);
         }

         // Gather requirements from the result type.
         auto *resultTypeRepr = [&subscr, &func]() -> TypeRepr * {
            if (subscr) {
               return subscr->getElementTypeLoc().getTypeRepr();
            } else if (auto *FD = dyn_cast<FuncDecl>(func)) {
               return FD->getBodyResultTypeLoc().getTypeRepr();
            } else {
               return nullptr;
            }
         }();
         if (resultTypeRepr && !isa<OpaqueReturnTypeRepr>(resultTypeRepr)) {
            auto resultType = resolution.resolveType(
               resultTypeRepr, TypeResolverContext::FunctionResult);

            inferenceSources.emplace_back(resultTypeRepr, resultType);
         }
      }
   } else if (auto *ext = dyn_cast<ExtensionDecl>(GC)) {
      // Form the interface type of the extension so we can use it as an inference
      // source.
      //
      // FIXME: Push this into the "get interface type" request.
      bool mustInferRequirements = false;
      Type extInterfaceType =
         formExtensionInterfaceType(ext, ext->getExtendedType(),
                                    gp, sameTypeReqs,
                                    mustInferRequirements);

      auto cannotReuseNominalSignature = [&]() -> bool {
         const auto finalDepth = gp->getParams().back()->getDepth();
         return mustInferRequirements
                || !sameTypeReqs.empty()
                || ext->getTrailingWhereClause()
                || (getExtendedTypeGenericDepth(ext) != finalDepth);
      };

      // Re-use the signature of the type being extended by default.
      if (!cannotReuseNominalSignature()) {
         return ext->getSelfNominalTypeDecl()->getGenericSignatureOfContext();
      }

      // Allow parameters to be equated with concrete types.
      allowConcreteGenericParams = true;
      // Extensions must occur at the top level, they have no
      // (valid) parent signature.
      parentSig = nullptr;
      inferenceSources.emplace_back(nullptr, extInterfaceType);
   }

   // EGREGIOUS HACK: The GSB cannot handle the addition of parent signatures
   // from malformed decls in many cases.  Check the invalid bit and null out the
   // parent signature.
   if (auto *DD = GC->getParent()->getAsDecl()) {
      parentSig = DD->isInvalid() ? nullptr : parentSig;
   }

   return TypeChecker::checkGenericSignature(
      gp, GC, parentSig,
      allowConcreteGenericParams,
      sameTypeReqs, inferenceSources);
}

///
/// Checking bound generic type arguments
///

RequirementCheckResult TypeChecker::checkGenericArguments(
   DeclContext *dc, SourceLoc loc, SourceLoc noteLoc, Type owner,
   TypeArrayView<GenericTypeParamType> genericParams,
   ArrayRef<Requirement> requirements,
   TypeSubstitutionFn substitutions,
   LookupConformanceFn conformances,
   ConformanceCheckOptions conformanceOptions,
   GenericRequirementsCheckListener *listener,
   SubstOptions options) {
   bool valid = true;

   // We handle any conditional requirements ourselves.
   conformanceOptions |= ConformanceCheckFlags::SkipConditionalRequirements;

   struct RequirementSet {
      ArrayRef<Requirement> Requirements;
      SmallVector<ParentConditionalConformance, 4> Parents;
   };

   SmallVector<RequirementSet, 8> pendingReqs;
   pendingReqs.push_back({requirements, {}});

   AstContext &ctx = dc->getAstContext();
   while (!pendingReqs.empty()) {
      auto current = pendingReqs.pop_back_val();

      for (const auto &rawReq : current.Requirements) {
         auto req = rawReq;
         if (current.Parents.empty()) {
            auto substed = rawReq.subst(substitutions, conformances, options);
            if (!substed) {
               // Another requirement will fail later; just continue.
               valid = false;
               continue;
            }

            req = *substed;
         }

         auto kind = req.getKind();
         Type rawFirstType = rawReq.getFirstType();
         Type firstType = req.getFirstType();
         if (firstType->hasTypeParameter())
            firstType = dc->mapTypeIntoContext(firstType);

         Type rawSecondType, secondType;
         if (kind != RequirementKind::Layout) {
            rawSecondType = rawReq.getSecondType();
            secondType = req.getSecondType();
            if (secondType->hasTypeParameter())
               secondType = dc->mapTypeIntoContext(secondType);
         }

         // Don't do further checking on error types.
         if (firstType->hasError() || (secondType && secondType->hasError())) {
            // Another requirement will fail later; just continue.
            valid = false;
            continue;
         }

         bool requirementFailure = false;
         if (listener && !listener->shouldCheck(kind, firstType, secondType))
            continue;

         Diag<Type, Type, Type> diagnostic;
         Diag<Type, Type, StringRef> diagnosticNote;

         switch (kind) {
            case RequirementKind::Conformance: {
               // Interface conformance requirements.
               auto proto = secondType->castTo<InterfaceType>();
               // FIXME: This should track whether this should result in a private
               // or non-private dependency.
               // FIXME: Do we really need "used" at this point?
               // FIXME: Poor location information. How much better can we do here?
               // FIXME: This call should support listener to be able to properly
               //        diagnose problems with conformances.
               auto conformance = conformsToInterface(firstType, proto->getDecl(), dc,
                                                      conformanceOptions, loc);

               if (conformance) {
                  // Report the conformance.
                  if (listener && valid && current.Parents.empty()) {
                     listener->satisfiedConformance(rawFirstType, firstType,
                                                    conformance);
                  }

                  auto conditionalReqs = conformance.getConditionalRequirements();
                  if (!conditionalReqs.empty()) {
                     auto history = current.Parents;
                     history.push_back({firstType, proto});
                     pendingReqs.push_back({conditionalReqs, std::move(history)});
                  }
                  continue;
               }

               // A failure at the top level is diagnosed elsewhere.
               if (current.Parents.empty())
                  return RequirementCheckResult::Failure;

               // Failure needs to emit a diagnostic.
               diagnostic = diag::type_does_not_conform_owner;
               diagnosticNote = diag::type_does_not_inherit_or_conform_requirement;
               requirementFailure = true;
               break;
            }

            case RequirementKind::Layout:
               // TODO: Statically check other layout constraints, once they can
               // be spelled in Swift.
               if (req.getLayoutConstraint()->isClass() &&
                   !firstType->satisfiesClassConstraint()) {
                  diagnostic = diag::type_is_not_a_class;
                  diagnosticNote = diag::anyobject_requirement;
                  requirementFailure = true;
               }
               break;

            case RequirementKind::Superclass: {
               // Superclass requirements.
               if (!secondType->isExactSuperclassOf(firstType)) {
                  diagnostic = diag::type_does_not_inherit;
                  diagnosticNote = diag::type_does_not_inherit_or_conform_requirement;
                  requirementFailure = true;
               }
               break;
            }

            case RequirementKind::SameType:
               if (!firstType->isEqual(secondType)) {
                  diagnostic = diag::types_not_equal;
                  diagnosticNote = diag::types_not_equal_requirement;
                  requirementFailure = true;
               }
               break;
         }

         if (!requirementFailure)
            continue;

         if (listener &&
             listener->diagnoseUnsatisfiedRequirement(rawReq, firstType,
                                                      secondType, current.Parents))
            return RequirementCheckResult::Failure;

         if (loc.isValid()) {
            // FIXME: Poor source-location information.
            ctx.Diags.diagnose(loc, diagnostic, owner, firstType, secondType);

            std::string genericParamBindingsText;
            if (!genericParams.empty()) {
               genericParamBindingsText =
                  gatherGenericParamBindingsText(
                     {rawFirstType, rawSecondType}, genericParams, substitutions);
            }
            ctx.Diags.diagnose(noteLoc, diagnosticNote, rawFirstType, rawSecondType,
                               genericParamBindingsText);

            ParentConditionalConformance::diagnoseConformanceStack(
               ctx.Diags, noteLoc, current.Parents);
         }

         return RequirementCheckResult::Failure;
      }
   }

   if (valid)
      return RequirementCheckResult::Success;
   return RequirementCheckResult::SubstitutionFailure;
}

llvm::Expected<Requirement>
RequirementRequest::evaluate(Evaluator &evaluator,
                             WhereClauseOwner owner,
                             unsigned index,
                             TypeResolutionStage stage) const {
   // Figure out the type resolution.
   TypeResolutionOptions options = TypeResolverContext::GenericRequirement;
   Optional<TypeResolution> resolution;
   switch (stage) {
      case TypeResolutionStage::Structural:
         resolution = TypeResolution::forStructural(owner.dc);
         break;

      case TypeResolutionStage::Interface:
         resolution = TypeResolution::forInterface(owner.dc);
         break;

      case TypeResolutionStage::Contextual:
         llvm_unreachable("No clients care about this. Use mapTypeIntoContext()");
   }

   auto resolveType = [&](TypeLoc &typeLoc) -> Type {
      Type result;
      if (auto typeRepr = typeLoc.getTypeRepr())
         result = resolution->resolveType(typeRepr, options);
      else
         result = typeLoc.getType();

      return result ? result : ErrorType::get(owner.dc->getAstContext());
   };

   auto &reqRepr = getRequirement();
   switch (reqRepr.getKind()) {
      case RequirementReprKind::TypeConstraint: {
         Type subject = resolveType(reqRepr.getSubjectLoc());
         Type constraint = resolveType(reqRepr.getConstraintLoc());
         return Requirement(constraint->getClassOrBoundGenericClass()
                            ? RequirementKind::Superclass
                            : RequirementKind::Conformance,
                            subject, constraint);
      }

      case RequirementReprKind::SameType:
         return Requirement(RequirementKind::SameType,
                            resolveType(reqRepr.getFirstTypeLoc()),
                            resolveType(reqRepr.getSecondTypeLoc()));

      case RequirementReprKind::LayoutConstraint:
         return Requirement(RequirementKind::Layout,
                            resolveType(reqRepr.getSubjectLoc()),
                            reqRepr.getLayoutConstraint());
   }
   llvm_unreachable("unhandled kind");
}

llvm::Expected<Type>
StructuralTypeRequest::evaluate(Evaluator &evaluator,
                                TypeAliasDecl *typeAlias) const {
   TypeResolutionOptions options((typeAlias->getGenericParams()
                                  ? TypeResolverContext::GenericTypeAliasDecl
                                  : TypeResolverContext::TypeAliasDecl));

   if (!typeAlias->getDeclContext()->isCascadingContextForLookup(
      /*functionsAreNonCascading*/ true)) {
      options |= TypeResolutionFlags::KnownNonCascadingDependency;
   }

   // This can happen when code completion is attempted inside
   // of typealias underlying type e.g. `typealias F = () -> Int#^TOK^#`
   auto &ctx = typeAlias->getAstContext();
   auto underlyingTypeRepr = typeAlias->getUnderlyingTypeRepr();
   if (!underlyingTypeRepr) {
      typeAlias->setInvalid();
      return ErrorType::get(ctx);
   }

   auto resolution = TypeResolution::forStructural(typeAlias);
   auto type = resolution.resolveType(underlyingTypeRepr, options);

   auto genericSig = typeAlias->getGenericSignature();
   SubstitutionMap subs;
   if (genericSig)
      subs = genericSig->getIdentitySubstitutionMap();

   Type parent;
   auto parentDC = typeAlias->getDeclContext();
   if (parentDC->isTypeContext())
      parent = parentDC->getSelfInterfaceType();
   return TypeAliasType::get(typeAlias, parent, subs, type);
}
